package com.zjb.datastructure.sort;

import java.util.Arrays;
import java.util.List;

public class InsertionSort {

    static void sort(int[] datas) {
        for (int i = 1; i < datas.length; i++) {
            int temp = datas[i];
            int j = i - 1;
            //把比temp大的数字向后移动
            for (; j > 0; j--) {
                if (datas[j] > temp) {
                    datas[j + 1] = datas[j];
                } else {
                    break;
                }
            }
            //到这证明 datas[j] < temp
            datas[j + 1] = temp;
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 3, 4, 2, 1, 5};
        sort(a);
        for (int i : a) {

            System.out.print(i);
        }
    }
}
